#ifndef BUBBLESORT_H_INCLUDED
#define BUBBLESORT_H_INCLUDED

namespace ED{

    template<typename T>
    class Ordenacao{
        public:
        static void bubbleSort(T *vet, int n);
        static void heapsort(T *vet, int n);

        template<typename T>
        static void Ordenacao<T>::bubbleSort(T *vet, int n) {
            T temp;
            for (int i=n-1; i>0; i--)
            for (int j=0; j<i; j++)
            if (vet[j+1] < vet[j]) {
                temp = vet[j]; //
                vet[j] = vet[j+1]; // Troca de elementos
                vet[j+1] = temp; //
            }
        }

        template<typename T>
        static void Ordenacao<T>::heapsort(T *vet, int n) {
            int i;
            for(i= (n >> 1)-1; i>=0; i--)
                heapify(vet, i, n);
            for(i=n-1; i> 0; i--) {
                T aux = vet[0];
                vet[0] = vet[i];
                vet[i] = aux;
                heapify(vet, 0, i);
            }
        }

        private:
            void heapify(T *vet, int pai, int heapsize);

        template<typename T>
        void Ordenacao<T>::heapify(T *vet, int pai, int heapsize) {
            int fl, fr, imaior;
            fl = (pai << 1) + 1;
            fr = fl + 1;
            while(true) {
                if((fl < heapsize) && (vet[fl] > vet[pai]))
                    imaior = fl;
                else
                    imaior = pai;
                if((fr< heapsize) && (vet[fr] > vet[imaior]))
                    imaior= fr;
                if(imaior!= pai){
                    T aux = vet[pai];
                    vet[pai] = vet[imaior];
                    vet[imaior] = aux;
                    pai= imaior;
                    fl = (pai << 1) + 1;
                    fr = fl + 1;
                }else break;
            }
        }
    };

}
#endif // BUBBLESORT_H_INCLUDED
